home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8731 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: mail2news.demon.co.uk!genesis.demon.co.uk
  2. From: Lawrence Kirby <fred@genesis.demon.co.uk>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Efficient Sorting - In search of
  5. Date: Wed, 06 Mar 96 00:26:40 GMT
  6. Organization: none
  7. Message-ID: <826072000snz@genesis.demon.co.uk>
  8. References: <4h4imh$3bh@news.cis.nctu.edu.tw> <4h4rgs$f8l@news.Belgium.EU.net>
  9. Reply-To: fred@genesis.demon.co.uk
  10. X-NNTP-Posting-Host: genesis.demon.co.uk
  11. X-Newsreader: Demon Internet Simple News v1.27
  12. X-Mail2News-Path: genesis.demon.co.uk
  13.  
  14. In article <4h4rgs$f8l@news.Belgium.EU.net>
  15.            pahint@eunet.be "Pieter Hintjens" writes:
  16.  
  17. >Don Pierce (don@pierce.geometrics.com) wrote:
  18. >: I am looking for an efficient sorting algorithm
  19. >: that can sort an array of floats. I prefer
  20. >: a non-recursive version as I have heard they are
  21. >: not very efficient on large data sets. My arrays
  22. >: are up 10000 elements.
  23. >
  24. >Try the COMB SORT algorithm.  This is basically a
  25. >bubble sort, with a one line change that brings it
  26. >up to the same kind of speed as quicksort.
  27.  
  28. It is still likely to be slower than any reasonable version of qsort().
  29.  
  30. Combsort is one of those historical curiosities that has no practical use
  31. (much like bubble sort really). For small arrays (certainly up to 10000)
  32. shell sort is better. For anything larger you go to quicksort, heapsort or
  33. for lists, list merge sort. These are all on average at least twice as fast
  34. as combsort. Where you have very large arrays and spare space available you
  35. can use something like radix sort.
  36.  
  37. >I'd give you the algorithm in code, but my version
  38. >is in COBOL, and this is a C newsgroup...  ;-)
  39.  
  40. If your qsort() is poor get a decent one e.g. the GNU one or the one in
  41. Snippets (which is slightly better in my experience).
  42.  
  43. >Oops, my mistake - it's a *two* line change.
  44.  
  45. Shell sort is a similar modification of insertion sort. If you're regularly
  46. sorting lots of data it is worth grabbing code with a better algorithm.
  47.  
  48. -- 
  49. -----------------------------------------
  50. Lawrence Kirby | fred@genesis.demon.co.uk
  51. Wilts, England | 70734.126@compuserve.com
  52. -----------------------------------------
  53.